When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to the device driver software in a page description language, such as PostScript or PCL, which provide descriptions of the objects to be rendered onto the page, rather than a raster image to be printed Equivalently, a set of descriptions of graphics objects may be provided in function calls to a graphics interface, such as the Microsoft Windows™ GDI (Microsoft Corporation), or UNIX™ XII (The Open Group). The page is typically rendered for printing and/or display by an object-based graphics system (or Raster Image Processor).
Most of these object based graphics systems utilize a large area of memory, known to the art as a frame store or a page buffer, to hold a pixel-based image of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects that appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel by pixel basis. This is commonly known to the art as “Painter's algorithm”. Objects are considered in priority order, from the rearmost object to the foremost object. This priority order is sometime called a z-level or layer, indicative of a stack of objects. Typically, each object is rasterized in scan line order and pixels are written to the frame store in sequential runs along each scan line. Some graphics interfaces allow a logical or arithmetic operation to be specified, to be performed between one or more graphics objects and the already rendered pixels in the frame buffer. In these cases the principle remains the same: objects (or groups of objects) are rasterized in scan line order, and the result of the specified operation is calculated and written to the frame store in sequential runs along each scan line.
There are essentially two problems with this technique. The first is that it requires fast random access to all of the pixels in the frame store. This is because each new object could affect any pixel in the frame store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high-resolution color printers the amount of RAM required is very large, typically in excess of 100 Mbytes, which is costly and difficult to run at high speed. The second problem is that many pixels, which are painted (rendered), are over-painted (re-rendered) by later objects. Painting these pixels with the earlier objects is a waste of time.
One method for overcoming the large frame-store problem is the use of “banding”. When banding is used, only part of the fame store exists in memory at any one time. All of the objects to be drawn are retained in a “display list”, which is an internal representation of the information required to draw the objects on the page. The display list is considered in object order as above, and only those pixel operations which fall within the fraction of the page which is held in the band are actually performed. After all objects in the display list have been drawn, the band is sent to the printer (or to intermediate storage) and the process is repeated for the next band of the page. There are some penalties with this technique, however. For example, the objects being drawn must be reconsidered many times, once for each band. As the number of bands increases, so does the repetitious examination of the objects requiring rendering. Also, the technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all of the objects on the page are retained in a display list. On each scan line the objects which intersect that scan line are then considered in priority order and for each object, spans of pixels between the intersection points of the object edges with the scan line are filled in a line store. This technique overcomes the large frame store problem, however it still suffers from the over-painting problem.
Other graphic systems utilise pixel-sequential rendering to overcome both the large frame store problem and the over-painting problem. In these systems, each pixel is generated in raster order. Again, all objects to be drawn are retained in a display list. On each scan line, the edges of objects, which intersect that scan line, are held in increasing order of their intersection with the scan line. These points of intersection, or edge crossings, are considered in turn, and used to toggle an array of fields that indicate the activity of the objects in the display list. There is one activity field for each object painting operation that is of interest on the scan line. There is also a field to indicate operations that do not require previously generated data. Between each pair of edges considered, the color data for each pixel, which lies between the first edge and the second edge, is generated by using a priority encoder on the activity flags to determine which operations are required to generate the color, and performing only those operations for the span of pixels between the two edges. In preparation for the next scan line, the coordinate of intersection of each edge is updated in accordance with the nature of each edge, and the edges are sorted into increasing order of intersection with that scan line. Any new edges are also merged into the list of edges.
Graphic systems which use pixel-sequential rendering have significant advantages in that there is no frame store or line store, no unnecessary over-painting, and the object priorities are dealt with in constant order time by the priority encoder, rather than in order N time, where N is the number of priorities.
Australian Patent No. 743218, corresponding in disclosure to U.S. patent application Ser. No. 09/392,741, describes a pixel sequential rendering apparatus and notes that expression trees are often used to describe compositing operations that include variable transparency in the intersection region. Further, that document notes that one difficulty encountered with implementation is that, in many cases, rendering apparatus do not deal adequately with compositing of objects comprising pixels having associated opacity values. A solution proposed therein is to combine leaf and operator instructions into one unified instruction (ie. a level instruction), which contains both leaf and operator instructions in a single command. For a binary operation, this would only require 2 levels. The first level defines the right leaf object with a push operation (COPYPEN with STACK_STD_OP) and the second level defines the left leaf object with the operation to be applied on these 2 objects. The combined left leaf and operator allow the operand to be read and operated on the same clock cycle. This feature works well when both right and left leaves are active. However it complicates the expression tree when the left and right leaves are not the same shape because the simple expression tree will only be correct in the intersecting region.
An example of this is seen FIGS. 25A-25C for the compositing of two different objects. For the expression tree of FIG. 25A, when the objects A and B have the same shape and overlap, a compositing stack representation shown in FIG. 25B is very simple. When however, A and B have different shapes but still overlap, the resulting compositing stack as seen in FIG. 25C, is more complicated.
In this case, it is necessary to use clippings to force the compositing operation to be applied on the correct regions. This is typically achieved by separating the operator into another level and applying a clip to the operator. As the number of levels in the intersecting region becomes 3, the compositing of FIG. 25C will then take 3 clock cycles instead of 2 clock cycles in FIG. 25B.
The clippings can be direct edge clippings if the leaf object itself is a simple closed curve or rectangle. If the object is not a simple closed curve or a rectangle, it is necessary to sacrifice a level just for the clipping operation. This can become very complicated when a number of objects are composited together and the objects are not all active at the same time because they have different shapes. The operation on the top layer will need to be clipped by all objects under it in the priority order. Where the number of active priority levels becomes large, the clippings can become too complicated to manage.
FIGS. 26A-26C show an example of compositing 3 objects which produces four distinct and different areas of overlap. FIG. 26A shows the expression tree, FIG. 26C the corresponding compositing stack and FIG. 26B the resulting rendered image. FIGS. 27A-27C show corresponding representations for an example of compositing 4 objects with different overlapping shapes. The number inside each region in each of FIG. 26B and FIG. 27B indicates the number of clock cycles required to composite the corresponding region. In the region where all objects overlap, the number of clock cycles spent on compositing is seen to be almost double the number of objects.
Australian Patent Publication No. AU-A-35163/01, corresponding to U.S. patent application Ser. No. 09/836,226, describes a method for generating instructions for a directed acyclic graph (ie. an expression tree) comprising one or more parent nodes and one or more leaf nodes. That method generates operator instructions on the parent nodes and leaf instructions on the leaf nodes according to the activity state of that node. The generated instructions are passed through a number of processing stages in sequential order down to a fill generation stage which uses the leaf instructions to generate fill colors for leaf nodes. A sequentially following compositing stage then uses the leaf instructions to push the generated color to a compositing stack. The operator instructions pass through the fill generation stage and then are used by the compositing stage to perform operations defined by the parent nodes.
This method can generate the required instructions for those active nodes in groups of one or more pixel locations without the use of complicated clippings. However when all the objects are the same shape and overlap entirely, this method is less efficient than that described in the aforementioned Australian Patent No. 743218 because the number of clock cycles required for compositing is significantly more. Consider the expression tree in FIG. 28A, which is for the region A∩B∩C∩D of FIG. 28B. A truly optimised number of clock cycles is 4: ie. push A to stack, mul(B, stack), screen(C, stack) and darken(D, stack). The number of clock cycles required by the method of Australian Patent Publication No. AU-A-35163/01 is 7—each node needs a clock cycle.
The above methods have the common inefficiency in sending the redundant operator instructions to the fill generation stage and redundant leaf instructions to the compositing stage. A leaf instruction is only required to push the generated color to the compositing stack.